|
In the mathematical field of graph theory, the Foster graph is a bipartite 3-regular graph with 90 vertices and 135 edges. The Foster graph is Hamiltonian and has chromatic number 2, chromatic index 3, radius 8, diameter 8 and girth 10. It is also a 3-vertex-connected and 3-edge-connected graph. All the cubic distance-regular graphs are known.〔Brouwer, A. E.; Cohen, A. M.; and Neumaier, A. Distance-Regular Graphs. New York: Springer-Verlag, 1989.〕 The Foster graph is one of the 13 such graphs. It is the unique distance-transitive graph with intersection array .〔(Cubic distance-regular graphs ), A. Brouwer.〕 It can be constructed as the incidence graph of the partial linear space which is the unique triple cover with no 8-gons of the generalized quadrangle ''GQ''(2,2). It is named after R. M. Foster, whose ''Foster census'' of cubic symmetric graphs included this graph. ==Algebraic properties== The automorphism group of the Foster graph is a group of order 4320.〔Royle, G. (F090A data )〕 It acts transitively on the vertices, on the edges and on the arcs of the graph. Therefore the Foster graph is a symmetric graph. It has automorphisms that take any vertex to any other vertex and any edge to any other edge. According to the ''Foster census'', the Foster graph, referenced as F90A, is the only cubic symmetric graph on 90 vertices.〔Conder, M. and Dobcsányi, P. "Trivalent Symmetric Graphs Up to 768 Vertices." J. Combin. Math. Combin. Comput. 40, 41-63, 2002.〕 The characteristic polynomial of the Foster graph is equal to . 抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)』 ■ウィキペディアで「Foster graph」の詳細全文を読む スポンサード リンク
|